This invention relates to a decoder for multiple error correcting Reed-Solomon codes, that is to a Reed-Solomon decoder.
The Reed-Solomon code has been widely used as a code capable of correction of multiple errors in, for example, information stored in various mass storage devices and information transmitted in high-speed communication.
If a root of an equation W(z)=0 is .alpha. where W(z) is a primitive polynomial, then the Reed-Solomon code is a code over a Galois field whose primitive element is the root .alpha.. The Reed-Solomon code is one of the block error correcting codes. Here, let .alpha. be the primitive element of a Galois field GF(2.sup.m), and give consideration to a specific Reed-Solomon code having a code length n (n=2.sup.m -1) and having roots .alpha., .alpha..sup.2, . . . , .alpha..sup.2t. According to this Reed-Solomon code, m bits is one process unit, that is one symbol. The quantity of original information is n-2t symbols. In the following description, m=8 and one symbol is represented by eight bits, that is, one byte. A 1-packet received word is formed of n symbols. If t=8, this permits error correction of eight symbols.
The decoding of Reed-Solomon codes is carried out according to the following (i) to (vi) steps. However, when unreasonable results are yielded in the steps (iii)-(v), the judgement that uncorrectable errors have occurred is made.
(i) From the received polynomial Y(z) the coefficients of which are symbols in a received word, the calculation of 2t syndromes, that is, s1, s2, . . . , s2t, is performed by: EQU si=Y(.alpha..sup.i) (1)
Each syndrome si is an element of the Galois field GF(2.sup.m). The syndrome polynomial S(z) is defined by: EQU S(z)=s1+s2z+. . . +s2tz.sup.2t-1 (2)
(ii) If all the syndromes are zeros, the judgement that there occur no errors is made.
(iii) If there exists a non-zero syndrome, then an error locator polynomial .sigma.(z) and an error evaluator polynomial .omega.(z) are derived from the syndrome polynomial S(z). That is, when .phi.(z) is a polynomial, a polynomial .sigma.(z) of degree equal to or less than t and a polynomial .omega.(z) of degree equal to or less than t-1 are found which satisfy the following formulas (3) and (4) and which are elements each other. EQU .phi.(z)z.sup.2t +.sigma.(z)S(z)=.omega.(z) (3) EQU .sigma.(0)=1 (4)
(iv) k roots .alpha..sup.-ju (ju=j1, j2, . . . , jk) of an equation .sigma.(z)=0 are found (k.ltoreq.t). Here, k is the degree of the error locator polynomial .sigma.(z), representing the number of errors. If a method is employed which determines whether .sigma.(.alpha..sup.-i) is zero or not by substitution of each one of .alpha..sup.-i (i=0, 1, . . . , n) in .sigma.(z), this makes it possible to search all the roots. Such a method is called the Chien search. Each of the k roots .alpha..sup.-ju is the reciprocal of a so-called error locator.
(v) The derivative of the error locator polynomial .sigma.(z) (i.e., .sigma.'(z)) is obtained, and from the following formula (5) error values e1, e2, . . . , ek are found. EQU e.sub.u =-.omega.(.alpha..sup.-ju)/.sigma.'(.alpha..sup.-ju)(5)
Here, .omega.(.alpha..sup.-ju) is called the error evaluation value, while on the other hand .sigma.'(.alpha..sup.-ju) is called the error locator polynomial differential value.
(vi) Error locations j1, j2, . . . , jk are found from k roots .alpha..sup.-j1, .alpha..sup.-j2, . . . ,.alpha..sup.-jk, and errors in the received word are corrected by subtraction of the error values e1, e2, . . . , ek from symbols at the found error locations in the received word.
One of the methods for finding the error locator polynomial .sigma.(z) and the error evaluator polynomial .omega.(z) in the step (iii), is the Euclidean algorithm. The Euclidean algorithm is a procedure of finding .sigma.(z) and .omega.(z) by calculating the greatest common divisor polynomial of Z.sup.2t and S(z) by Euclidean algorithm arithmetic operations.
A procedure of the Euclidean algorithm arithmetic operation is now discussed below. In the following description, the degree of a polynomial X is expressed by degX. In the first place, four polynomials, denoted receptively A, B, L, and M, are initialized as follows. EQU A=Z.sup.2t (6) EQU B=S(z) (7) EQU L=0 (8) EQU M=1 (9)
If degA.gtoreq.degB, then the polynomials A and L are updated according to the following formulas (10) and (11) wherein a is the coefficient of the highest-degree term of the polynomial A and b is the coefficient of the highest-degree term of the polynomial B. EQU A=bA+aBz.sup.degA-degB (10) EQU L=bL+aMz.sup.degA-degB (11)
As a result of such updating, degA decreases while degL increases. Conversely, if degA&lt;degB, the polynomials B and M are updated according to the following formulas (12) and (13). EQU B=aB+bAz.sup.degB-degA (12) EQU M=aM+bLz.sup.degB-degA (13)
As a result of such updating, degB decreases while degM increases. If iteration of such operation produces the situation that degA.ltoreq.t-1, then .omega.(z)=A and .sigma.(z)=L. If degB.ltoreq.t-1, then .omega.(z)=B and .sigma.(z)=M. In this way, the error locator polynomial .sigma.(z) and the error evaluator polynomial .omega.(z) are found.
If degA.gtoreq.degB in the foregoing procedure, then the polynomials A and L are updated according to the formulas (14) and (15). EQU A=A+(a/b)Bz.sup.degA-degB (14) EQU L=L+(a/b)Mz.sub.degA-degB (15)
degA&lt;degB, then the polynomials B and M are updated according formulas (16) and (17). EQU B=B+(b/a)Az.sup.degB-degA (16) EQU M=M+(b/a)Lz.sup.degB-degA (17)
Such is hereinafter called the "improved algorithm".
Japanese patent application, published under no. 3-195216, shows a Euclidean algorithm arithmetic operation circuit with a systolic array structure.
In recent years, Reed-Solomon codes with the specification that the number of errors to be corrected (t) ranges from eight to sixteen have become generalized. This means a considerable increase in the amount of calculation required in the error correcting processing, therefore producing the problem that if Reed-Solomon decoders employ a systolic array structure the circuit scale increases with the number of correctable errors.